package offer.day21;

import java.util.Collection;

public class No35CopyComplexList {
    /*
     * 面试题35：复杂链表的复制
     *题目：请实现函数complexListNode* Clone(ComplexListNode* pHead),
     *	 复制一个复杂链表。在复杂链表中，每个节点除了有一个m_pNext指针指向下一个节点，还有一个m_pSibling指针指向链表中的任意节点或者null指针。
     *C++中节点定义为：
     *struct ComplexListNode{
     *	int m_nValue;
     *	ComplexListNode* m_pNext;
     *	ComplexListNode* m_pSibsling;
     *}
     *
     *第一种办法：
     *思路：1>复制每一个节点N为N'，并指向next
     *	 2>构建N'的sibling节点S'(从头查找sibling节点)
     *时间复杂度O(n2)  空间复杂度O(1)
     *
     *第二种办法：
     *思路：1>复制每一个节点N为N'，并指向next，构建一个哈希表，存储<N,N'>的配对信息
     *	 2>构建N'的sibling节点S'，直接查找哈希表，即可找到S'
     *时间复杂度O(n)   空间复杂度O(n)
     *
     *第三种办法： （下面实现的）
     *思路：1>将每个节点N进行复制为N',然后连接到每个N的next下
     *   2>然后根据每个N的sibling节点S，连接N’的sibling节点S',也就是S.sibling
     *   3>最后再将奇数个的节点连接到一起，就是原链表；将偶数个的节点连接到一起，就是复制的节点
     *   时间复杂度O(n)  空间复杂度O(1)
     *
     * */
    public static void main(String[] args) {
        No35CopyComplexList c = new No35CopyComplexList();
        ComplexListNode root = new ComplexListNode(1);
        ComplexListNode two = new ComplexListNode(2);
        ComplexListNode three = new ComplexListNode(3);
        ComplexListNode four = new ComplexListNode(4);
        ComplexListNode five = new ComplexListNode(5);

        root.next = two;
        root.sibling = three;

        two.next = three;
        two.sibling = five;

        three.next = four;
        three.sibling = null;

        four.next = five;
        four.sibling = two;

        five.next = null;
        five.sibling = null;

        //复制复杂链表

        ComplexListNode result = c.Clone(root);
        ComplexListNode print = result;
        System.out.println("输出每个节点的sibling节点：");
        while (print != null) {
            if (print.sibling != null) {
                System.out.println(print.val + "的sibling节点为:" + print.sibling.val);
            }
            print = print.next;
        }
    }


    public ComplexListNode Clone(ComplexListNode root) {
        //复制N’节点到N的next
        CloneNodes(root);
        //连接N‘节点的sibling节点到S'  其中S' = S.next
        ConnectSiblingNodes(root);
        //重新将链表连接,奇数个为原链表,偶数个为复制的链表
        return ReconnectNodes(root);
    }

    private void CloneNodes(ComplexListNode root) {
        if (root == null) return;
        ComplexListNode tempNode = root;
        while (tempNode != null) {
            ComplexListNode cloneNode = new ComplexListNode(tempNode.val);
            cloneNode.next = tempNode.next;
            cloneNode.sibling = null;
            tempNode.next = cloneNode;
            tempNode = cloneNode.next;
        }
    }

    private void ConnectSiblingNodes(ComplexListNode root) {
        ComplexListNode tempNode = root;
        while (tempNode != null) {
            ComplexListNode cloneNode = tempNode.next;
            if (tempNode.sibling != null) {
                cloneNode.sibling = tempNode.sibling.next;
            }
            tempNode = cloneNode.next;
        }
    }

    private ComplexListNode ReconnectNodes(ComplexListNode root) {
        ComplexListNode oriNode = root;
        ComplexListNode cloneNode = null, cloneRoot = null;
        if (oriNode != null) {
            cloneRoot = cloneNode = oriNode.next;
            oriNode.next = cloneNode.next;
            oriNode = oriNode.next;
        }
        while (oriNode != null) {
            cloneNode.next = oriNode.next;
            cloneNode = cloneNode.next;
            oriNode.next = cloneNode.next;
            oriNode = oriNode.next;
        }
        return cloneRoot;
    }


}
